package pri.zjy.interview;

/**
 * @author zhangjy
 * @description
 * @date 2025/6/12 18:59
 */
public class Test8 {

    /**
     * public static class Node{
     * private Node next;
     * }
     * <p>
     * public static boolean hasCycle(Node node){
     * <p>
     * }
     */

    public static void main(String[] args) {
//        int[] nums = {3, 2, 1};
        int[] nums = {3, 5, 2, 1, 7};
        bubbleSort(nums);
        for (int i = 0; i < nums.length; i++) {
            System.out.println(nums[i]);
        }
    }

    public static class Node {

        private Node next;

    }

    public static boolean hasCycle(Node node) {
        if (node == null || node.next == null) return false;
        // 判断是否有环

        // 1 2 3 4
        // 快慢指针，slow走一步，fast走两步
        // 追上表明有环
        Node slow = node;
        Node fast = node.next;
        while (fast.next != null && fast.next.next != null) {
            if (slow == fast) return true;

            slow = slow.next;
            fast = fast.next.next;
        }

        return false;

    }

    /**
     * 选择排序
     * <p>
     * 思路：
     * 1.外层循环：从第一个元素到最后一个元素，逐步确定每个位置的最小值。
     * 2.内层循环：从当前位置的下一个元素开始，寻找比当前元素更小的值。
     * 3.交换逻辑：一旦找到更小的值，立即交换当前元素与较小值的位置。
     */
    public static void selectionSort(int[] numbers) {
        for (int i = 0; i < numbers.length; i++) {
            // 3, 4, 2, 1
            for (int j = i + 1; j < numbers.length; j++) {
                // nums[j]更小，则交换i、j位置
                if (numbers[j] < numbers[i]) {
                    int temp = numbers[j];
                    numbers[j] = numbers[i];
                    numbers[i] = temp;
                }
            }
        }

    }

    /**
     * 冒泡排序
     * <p>
     * 思路：
     * 1.外层循环：控制排序的轮数，每轮将一个最大元素 “冒泡” 到末尾。
     * 2.内层循环：从第一个元素开始，依次比较【相邻】元素，将较大值向后交换。
     * 3.循环边界：j < numbers.length - i - 1 确保每轮比较范围逐渐缩小。
     * 内存循环是j < numbers.length - i - 1，防止出现数组越界，并且提高性能（减少比较次数）。
     */
    public static void bubbleSort(int[] numbers) {
        // 每一轮 把一个元素 冒泡到最前面

        for (int i = 0; i < numbers.length; i++) {
            for (int j = 0; j < numbers.length - i - 1; j++) {
                // nums[j+1]更小，则交换j+1、j位置
                if (numbers[j + 1] < numbers[j]) {
                    int temp = numbers[j];
                    numbers[j] = numbers[j + 1];
                    numbers[j + 1] = temp;
                }
            }
        }
    }

}
